package leetcode.editor.cn.q1_300.q100;

/**
 * @author qidi
 * @date 2022-01-07 13:39:27
 */
class Q0116_PopulatingNextRightPointersInEachNode {

    static class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public Node connect(Node root) {
            if (root == null || root.left == null) return root;

            Node cur = root;

            // 下层最左的节点
            Node nextLevelLeft = cur.left;
            while (cur != null) {
                if (nextLevelLeft == null) break;

                cur.left.next = cur.right;
                if (cur.next != null) {
                    cur.right.next = cur.next.left;
                    cur = cur.next;
                } else {
                    cur = nextLevelLeft;
                    nextLevelLeft = cur.left;
                }
            }

            return root;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0116_PopulatingNextRightPointersInEachNode().new Solution();
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        solution.connect(node1);
    }
}